#ifndef 链栈
#define 链栈

template <typename Elemtype>
struct LinkNode
{
    Elemtype data;            // 存放栈中元素
    LinkNode<Elemtype> *next; // 栈顶指针
};

// 带头结点
template <typename T>
void InitStack(LinkNode<T> *s)
{
    s->next = nullptr;
}

template <typename T>
bool StackEmpty(const LinkNode<T> *s)
{
    return s->next == nullptr;
}

template <typename T>
bool Push(LinkNode<T> *s, const T &x)
{
    LinkNode<T> *p = new LinkNode<T>;
    p->data = x;
    p->next = StackEmpty(s) ? nullptr : s->next;
    s->next = p;
    return true;
}

template <typename T>
bool Pop(LinkNode<T> *s, T &x)
{
    if (StackEmpty(s))
    {
        return false;
    }

    x = s->next->data;
    LinkNode<T> *p = s->next;
    s->next = s->next->next;
    delete p;
    return true;
}

template <typename T>
bool GetTop(const LinkNode<T> *s, T &x)
{
    if (StackEmpty(s))
    {
        return false;
    }
    x = s->next->data;
    return true;
}

template <typename T>
void DestoryStack(LinkNode<T> *&s)
{
    if (!StackEmpty(s))
    {
        LinkNode<T> *p1 = s;
        do
        {
            s = p1->next;
            delete p1;
        } while (p1 = s);
    }
    s = nullptr;
}

#endif